package graph;

import geocoding.ALGOTrip;

import java.util.Enumeration;
import java.util.Stack;
import java.util.Vector;

public class DepthFirstGraph extends SearchableGraph {
	 /**
     * implementation of the depth-first algorithm for computing routes in the
     * bus network
     */

	private int edgeCount;
	
	public DepthFirstGraph() {
		super();
		
		edgeCount = 0;
	}
	
	public void initSearch(ALGONode startNode, ALGONode targetNode) {
		ALGOEdge [] succ = this.getEdgesForNode(startNode.getNodeID());
		
		for (int i = 0; i < succ.length; i++) {
			agenda.insert(new ALGOPathHeapData(new ALGOPath(succ[i]), -edgeCount));
			
			edgeCount ++;
		}
		
		currentNode = startNode;
		((ALGOPlacemarkNode)currentNode).putOnClosedList();
		this.targetNode = targetNode;
	}
	
	public boolean solutionFound() {
		return (currentNode == targetNode);
	}
	
	public boolean noSolution() {
		return (!solutionFound() && agenda.isEmpty());
	}
	
	public void nextStep() {
		if (!agenda.isEmpty()) {
			ALGOPath p = ((ALGOPathHeapData)agenda.retrieve()).getData();
			agenda.deleteHighest();
			ALGOEdge e = p.lastElement();
			
			currentNode = (ALGOPlacemarkNode)this.getNode(e.getSink());
			if (solutionFound()) {
				currentSolution = p;
				return;
			}
			
			ALGOEdge [] edges = this.getEdgesForNode(e.getSink());
		
			for (int i = 0; i < edges.length; i++) {
				currentNode = (ALGOPlacemarkNode)this.getNode(edges[i].getSink());
				System.out.println(((ALGOPlacemarkNode)currentNode).getValue().getName());
				if (!((ALGOPlacemarkNode)currentNode).isClosed()) {
					((ALGOPlacemarkNode)currentNode).putOnClosedList();
					ALGOPath p1 = new ALGOPath(p);
					p1.add(edges[i]);
					agenda.insert(new ALGOPathHeapData(p1, -edgeCount));
					edgeCount ++;
					System.out.println("new path");
				}
				else System.out.println("already visited");
				
				if (solutionFound()) {
					currentSolution = ((ALGOPathHeapData)agenda.retrieve()).getData();
					agenda.deleteHighest();
					return;
				}
			}
		}
	}
		
    public ALGOTrip computeBestPath(ALGOPlacemarkNode startNode, ALGOPlacemarkNode targetNode) {
		return computeShortestPath(startNode, targetNode);
    }
}
